package com.cty._02_HighQualityCode._25_MergeSortedLists;

/**
 * @Auther: cty
 * @Date: 2020/7/9 11:09
 * @Description: 面试题25：合并两个排序的链表
 * 题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按
 * 照递增排序的。例如输入图3.11中的链表1和链表2，则合并之后的升序链表如链
 * 表3所示。
 * @version: 1.0
 */

class ListNode{
    int value;
    ListNode next;

    public ListNode(){}

    public ListNode(int value){
        this.value = value;
    }
}  // end class

class LinkedList{
    private ListNode first;
    private ListNode last;

    public LinkedList(){
        first = null;
        last = null;
    }

    public boolean isEmpty(){
        return first == null;
    }

    public void displayList(){
        ListNode current = first;
        while(current != null){
            System.out.print(current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    public int findFirst(){
        if(isEmpty())
            return -1;

        return first.value;
    }

    public int deleteFirst(){
        if(isEmpty())
            return -1;

        int value = first.value;
        first = first.next;

        if(isEmpty())
            last = null;

        return value;
    }

    public void insertLast(int value){
        ListNode newNode = new ListNode(value);

        if(isEmpty())
            first = newNode;
        else
            last.next = newNode;
        last = newNode;
    }

    public LinkedList mergeSortedLists(LinkedList listA, LinkedList listB){
        if((listA == null || listA.isEmpty()) && (listB == null || listB.isEmpty()))
            return null;
        if((listA != null || !listA.isEmpty()) && (listB == null || listB.isEmpty()))
            return listA;
        if((listA == null || listA.isEmpty()) && (listB != null || !listB.isEmpty()))
            return listB;

        LinkedList mergeList = new LinkedList();
        while(!listA.isEmpty() && !listB.isEmpty()){
            if(listA.findFirst() <= listB.findFirst())
                mergeList.insertLast(listA.deleteFirst());
            else
                mergeList.insertLast(listB.deleteFirst());
        }

        while(!listA.isEmpty())
            mergeList.insertLast(listA.deleteFirst());

        while(!listB.isEmpty())
            mergeList.insertLast(listB.deleteFirst());

        return mergeList;
    }

}  // end class
